package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0152 
* @author      : ganwei 
* @date        : 2020年5月21日 
* @Description : 152. 乘积最大子数组 
*/
public class Leetcode0152 {
    /**
     * -解题思路，超出内存限制
     */
	public int maxProduct(int[] nums) {
		if(nums.length == 0) {
			return 0;
		}
		
    	int[][] dp = new int[nums.length][nums.length];
    	int max = Integer.MIN_VALUE;
    	for(int i = 0; i < nums.length; i++) {
    		dp[i][i] = nums[i];
    		max = Math.max(max, dp[i][i]);
    	}
		
    	
    	
    	for(int i = 0; i < nums.length-1; i++) {
    		for(int j = i+1; j < nums.length; j++) {
    			dp[i][j] = dp[i][j-1] * dp[j][j];
    			max = Math.max(max, dp[i][j]);
    		}
    	}
		return max;
    }
	
	public int maxProduct_1(int[] nums) {
		if(nums.length == 0) {
			return 0;
		}
		int[] dpmax = new int[nums.length];
		int[] dpmin = new int[nums.length];
		
		dpmax[0] = nums[0];
		dpmin[0] = nums[0];
		
		int max = nums[0];
		for(int i = 1; i < nums.length; i++) {
			dpmax[i] = Math.max(dpmin[i - 1] * nums[i], Math.max(dpmax[i - 1] * nums[i], nums[i]));
			dpmin[i] = Math.min(dpmin[i - 1] * nums[i], Math.min(dpmax[i - 1] * nums[i], nums[i]));
			max = Math.max(max, dpmax[i]);
		}
		
		return max;
	}
	
	public static void main(String[] args) {
		Leetcode0152 l0152 = new Leetcode0152();
		int[] nums = {2,-5,-2,-4,3};
		
		System.out.println(l0152.maxProduct_1(nums));
	}
    
}
